﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace eda12136309
{
    class AlgorithmLibrary
    {
        public static int[] insertionSort(int[] A)
        {
            for (int j = 0; j < A.Length; j++)
            {
                int key = A[j];
                int i = j - 1;
                while (i > -1 && A[i] > key)
                {
                    A[i + 1] = A[i];
                    i = i - 1;
                }
                A[i + 1] = key;
            }

            return A;
        }

        public static int[] bubbleSort(int[] A)
        {
            for (int i = 0; i < A.Length - 2; i++)
            {
                for (int j = A.Length - 1; j > i; j--)
                {
                    if (A[j] < A[j - 1])
                    {
                        int t = A[j];
                        A[j] = A[j - 1];
                        A[j - 1] = t;
                    }
                }
            }

            return A;
        }

        public static int[] heapSort(int[] A)
        {
            A = AlgorithmLibrary.heapify(A);

            int listSize = A.Length - 1;

            while (listSize > 0)
            {
                int t = A[listSize];
                A[listSize] = A[0];
                A[0] = t;
                listSize--;
                A = AlgorithmLibrary.shiftDown(A, 0, listSize);
            }

            return A;
        }

        private static int[] heapify(int[] A)
        {
            int start = (int) Math.Floor((A.Length - 1) / 2.0);

            while (start >= 0)
            {
                A = AlgorithmLibrary.shiftDown(A, start, A.Length - 1);
                start--;
            }

            return A;
        }

        private static int[] shiftDown(int[] A, int root, int listSize)
        {
            while (root * 2 + 1 <= listSize)
            {
                int child = root * 2 + 1;
                int t1 = root;

                if (A[t1] < A[child])
                {
                    t1 = child;
                }

                if ((child + 1 <= listSize) && (A[t1] < A[child + 1]))
                {
                    t1 = child + 1;
                }

                if (t1 != root)
                {
                    int t2 = A[root];
                    A[root] = A[t1];
                    A[t1] = t2;
                    root = t1;
                }
                else
                {
                    break;
                }
            }

            return A;
        }

        public static int[] mergeSort(int[] A, int p, int r)
        {
            if (p < r)
            {
                int q = (int)Math.Floor((p + r) / 2.0);
                A = mergeSort(A, p, q);
                A = mergeSort(A, q + 1, r);
                A = merge(A, p, q, r);
            }

            return A;
        }

        private static int[] merge(int[] A, int p, int q, int r)
        {
            int n1 = q - p + 1;
            int n2 = r - q;

            int[] L = new int[n1 + 1];
            int[] R = new int[n2 + 1];

            for (int z = 0; z < n1; z++)
            {
                L[z] = A[p + z];
            }

            for (int z = 0; z < n2; z++)
            {
                R[z] = A[q + z + 1];
            }

            L[n1 + 0] = int.MaxValue;
            R[n2 + 0] = int.MaxValue;

            int i = 0;
            int j = 0;

            for (int k = p; k <= r; k++)
            {
                if (L[i] <= R[j])
                {
                    A[k] = L[i];
                    i++;
                }
                else
                {
                    A[k] = R[j];
                    j++;
                }
            }

            return A;
        }

        public static int[] quickSort(int[] A, int p, int r)
        {
            if (p < r)
            {
                int q = partition(A, p, r);
                A = AlgorithmLibrary.quickSort(A, p, q - 1);
                A = AlgorithmLibrary.quickSort(A, q + 1, r);
            }

            return A;
        }

        private static int partition(int[] A, int p, int r)
        {
            int x = A[r];
            int i = p - 1;

            for (int j = p; j < (r - 0); j++)
            {
                if (A[j] <= x)
                {
                    i++;
                    int t1 = A[i];
                    A[i] = A[j];
                    A[j] = t1;
                }
            }

            int t2 = A[i + 1];
            A[i + 1] = A[r];
            A[r] = t2;

            return i + 1;
        }
    }
}
